#include <iostream>

const int capacity = 10;
class MaxHeap
{
public:
    // 构造
    MaxHeap():size(0) {}

    // 插入
    void Insert(int value)
    {
        array[size] = value;
        SiftUp(size);
        size++;
    }

    // 删除（删除根）
    void RemoveRoot()
    {
        if(size == 0)
            return;
        array[0] = array[--size];
        SiftDown(0); // 把根下沉
    }

    // show
    void show()
    {
        for(int i = 0; i < size; i++)
        {
            std::cout<<array[i]<< " ";
        }
        std::cout<<std::endl;
    }

private:
    // 写堆的时候先写这三个
    // 完全二叉树通用接口（获取双亲和左右孩子下标）
    int GetParent(int i) {return(i - 1) / 2;}
    int GetLeftChild(int i) {return 2 * i + 1;}
    int GetRightChild(int i) {return 2 * i + 2;}
    
    // 上浮操作
    void SiftUp(int i) 
    {
        while(i > 0 && array[i] > array[GetParent(i)])
        {
            std::swap(array[i], array[GetParent(i)]);
            i = GetParent(i);
        }
    }

    // 下沉操作
    void SiftDown(int i) 
    {
        int leftChild = GetLeftChild(i);
        int rightChild = GetRightChild(i);

        int Max = i;
        // 左孩子存在且值比我大
        if(leftChild < size && array[leftChild] > array[i])
        {
            Max = leftChild;
        }

        // 右孩子存在且比我和左孩子的较大值大
        if(rightChild < size && array[rightChild] > array[Max])
        {
            Max = rightChild;
        }

        // 递归条件
        if(Max != i)
        {
            std::swap(array[i], array[Max]);
            SiftDown(Max);
        }
    }
    int array[capacity];
    int size; // 当前数组元素个数
};

int main()
{
    MaxHeap h;
    for(int i = 0; i < 10; i++)
    {
        h.Insert(i + 1);
    }

    h.show();

    h.RemoveRoot();
    h.show();
    return 0;
}
